package com.practice.sort;

/**
 * Given a sequence and a value, divide the sequence to three parts:
 * >val, =val and <val.
 *
 */
public class Divide3 {
	public void divide(int[] a, int val) {
		int N = a.length;
		int i = -1;
		int k = N;
		
		for (int j=0; j<k; j++) {
			if (a[j] > val) {
				k--;
				swap(a, j, k);
				j--;
			}
			else if (a[j] < val) {
				i++;
				swap(a, i, j);
			}
		}
	}
	
	private void swap(int[] a, int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}
